The present invention is in the field of frequency offset and time offset estimation, as for example, carried out for synchronization purposes in spread spectrum receivers.
As common in conventional receivers, synchronization to receive signals is needed in order to properly detect data. Especially systems with mobile transmitters or receivers, frequency offset estimation for Doppler frequency shift compensation purposes is also carried out. For example, in CDMA (Code Division Multiple Access) systems, a signal acquisition process is carried out. Particularly in GNSS (Global Navigation Satellite System) systems, receivers may have to synchronize in frequency and time to the received signals. This signal acquisition is carried out prior to identification of different transmitters, in mobile communication systems prior to separation of different users, spreading sequences or pseudo-random codes, of which signals may be comprised in the overall received signal. This can, for example, be done by correlation receivers or processors, which target to match an incoming code comprised in the received signal with a known code stored in the receiver.
A problem for such conventional systems arises, due to mobility of transmitters or receivers, reflectors respectively. These may evoke an unknown Doppler effect which may render the correlation process useless if the modulation or distortion, which is evoked by the Doppler frequency is not removed. Therefore, conventional systems may have to spend high efforts and processing powers, in order to determine the Doppler frequencies for Doppler frequency compensation or equalization.
Conventional systems may subdivide an acquisition process in a two-dimensional search. On the one hand, they may carry out a time search along the time axis, in order to achieve synchronization with the beginning of e.g. a PN-code (Pseudo-Noise). Moreover, on the other hand a frequency search along the frequency axis may be carried out, in order to enable Doppler frequency removal or, generally, compensation of frequency shifts.
The following equation defines a simplified base-band signal in order to illustrate this process,
                              BB_signal          ⁢                      (            t            )                          =                                            ∑                              i                =                1                            N                        ⁢                                          A                i                            ⁢                                                                    D                    i                                    ⁡                                      (                                          t                      -                                              τ                        i                                                              )                                                  ·                                                      C                    i                                    ⁡                                      (                                          t                      -                                              τ                        i                                                              )                                                  ·                                  exp                  ⁡                                      (                                          j2π                      ⁢                                                                                          ⁢                                              f                        D                        i                                            ⁢                      t                                        )                                                                                +                                    n              ⁡                              (                t                )                                      .                                              (        1        )            
N represents the number of codes or transmitters present in the received signal, where one code or transmitter is indexed by i. Ai corresponds to the amplitude of code or transmitter i. Ci(t) represents a respective pseudo-random code. Di(t) represents the modulating data. τi and fDi are the two parameters, the time shift and the frequency shift, that the acquisition process is seeking to determine for each of the transmitters, codes respectively. Noise is represented by n(t), for example, n(t) may correspond to additive white Gaussian noise (AWGN). Alternatively, the processing, which will be described in the following can be carried out in an intermediate frequency band. The according intermediate frequency signal can be defined as
                                          IF_signal            ⁢                          (              t              )                                =                                                    ∑                                  i                  =                  1                                N                            ⁢                                                A                  i                                ⁢                                                                            D                      i                                        ⁡                                          (                                              t                        -                                                  τ                          i                                                                    )                                                        ·                                                            C                      i                                        ⁡                                          (                                              t                        -                                                  τ                          i                                                                    )                                                        ·                                      exp                    ⁡                                          (                                                                        j2π                          ⁡                                                      (                                                                                          f                                D                                i                                                            +                                                              f                                IF                                                                                      )                                                                          ⁢                        t                                            )                                                                                            +                          n              ⁡                              (                t                )                                                    ,                            (                  1          ⁢          a                )            wherein fIF defines the intermediate frequency.
In order to enable proper equalization or compensation the time shift and the frequency shift have to be determined with a certain accuracy. In conventional systems the accuracy needed for these values defines a certain step width within a possible range, which in turn is based on the system's characteristics and parameters.
As an example for a conventional system, GPS (Global Positioning System) will be illuminated in the following. For GPS the Doppler range is defined within −5 kHz and 5 kHz, i.e. a total bandwidth of 10 kHz, for a static user. Typically, this step width in which a frequency search is carried out is typically 500 Hz. The step width may be defined by the coherent integration time using for example
                                          f            step                    =                      2                          3              ·                              T                coh                                                    ,                            (        2        )            wherein fstep defines step width and Tcoh corresponds to the coherence time. More information about the integration time of acquisition algorithm, especially about long integration times, can, for example, be found in “Block Acquisition of Weak GPS signals in a Software Receiver” by Mark L. Psiaki.
In the following, the step width within the considered Doppler range will also be referred to as “Doppler bins”. For the example of GPS the time search range is typically 1 ms, which also equals the duration of one pseudo-random code sequence. The precision within which synchronization may be carried out depends on the chip rate of the code, where a minimum precision is two samples per chip. In a GPS PN-code there are 1023 chips in the L1-band. Thus, the time search will have to be done with at least 2×1023=2046 steps, and typically 4×1023=4092 steps are used. In the following these steps will also be referred to as “code bins”.
FIG. 5 illustrates a two-dimensional search plane. FIG. 5 shows a coordinate system in which the abscissa represents the time domain and the ordinate represents the frequency domain. The grid shown within the two-dimensional search plane or search space represents the number of Doppler bin and code bin combinations, which may be searched in a conventional GPS system. As an example, FIG. 5 shows N code bins and a Doppler frequency range of −5 kHz to 5 kHz. Moreover, in FIG. 5 it is assumed that the N code bins represent 1 ms.
When searching for the correlation value throughout the search plane depicted in FIG. 5, a signal can be detected when a correlation value in one of the depicted cells exceeds a certain noise threshold. FIG. 6 depicts correlation values over the two-dimensional search space or plane. The signal depicted in FIG. 6 is an example signal of correlation values from a received GPS signal. As can be seen from FIG. 6, the correlation peak can be easily distinguished.
In the following, some basic conventional acquisition methods will be described. Generally, detailed explanations of acquisition methods can be found in “A Software-Defined GPS and Galileo Receiver, A Single Frequency Approach” by Kai Bone, Dennis M. Akos, Nicolaj Bertelsen, Peter Rinder, Soren Holdt Jensen. One conventional method, is the so-called serial search acquisition. This method is often used in CDMA systems. It searches for the correlation peak within the two-dimensional space depicted in FIG. 6 cell by cell, i.e. all combinations of time shifts and frequency shifts are considered one after the other. The algorithm is further detailed by the block diagram shown in FIG. 7.
As shown in FIG. 7, multiplier 702 multiplies an incoming signal with a locally generated code, which is generated by the PRN (Pseudo-random Noise) code generator 704. The incoming signal may correspond to a CDMA signal. In other words, according to equation 1 as described above, the incoming signal may be a superposition of multiple code sequences. The locally generated PRN code corresponds to one single time shift. In other words, the PRN code generator 704 generates codes with different time shifts, more specifically, one code for which the acquisition is carried out is generated by the PRN code generator 704 over and over again, however, with different time shifts according to the above described code bins. For each of the time shifted versions of this code, another output will be produced by the multiplier 702.
The output of the multiplier 702 is input into two more multipliers 706 and 708, where the signal is multiplied with a locally generated carrier signal, its quadrature component, respectively. As can be seen in FIG. 7, the carrier signal is locally generated by local oscillator 710 and corresponds to one frequency bin or frequency shift. Its quadrature component is produced by the phase shifter 712 before being multiplied with the output of the multiplier 702. The results are the in-phase and quadrature components for one time shift and frequency shift combination, i.e. one combination of a code bin and a frequency bin. The two outputs of the multiplier 706 and 708 are then accumulated in the accumulators 714 and 716 before their respective powers are evaluated by the processing blocks 718 and 720. The power signals are then added by adder 722, resulting in the output signal for one frequency bin and code bin combination, i.e., referring to FIG. 6, for one correlation value for one cell.
According to the above description, the correlation peaks have to be searched on every cell, one by one, therefore, the number of combinations, which have to be considered is very high. This represents a main disadvantage of the serial method. In the following two more methods will be described, which at least partly parallelize the search in one of the dimensions, time or frequency, making use of a FFT (Fast Fourier Transformation) algorithm.
FIG. 8 illustrates a conventional method, which parallelizes the frequency domain search for the acquisition algorithm. FIG. 8 shows that the multiplier 802 multiplies the incoming signal with a locally generated version of the PRN code. The locally generated PRN code is generated by the PRN code generator 804. Again, the incoming signal is multiplied with the code representing a certain user or transmitter, where every single code bin, i.e. time shift, has to be considered. As soon as the incoming code happens to be aligned with the self-generated code, then a peak will be seen and a result of the FFT, which is carried out in block 806. The peak detection can be carried out by considering the power density indicated by the squared magnitudes within block 808. The peak at the output of the FFT shows a Doppler effect that a concrete user suffers, i.e. the frequency shift or frequency bin that is associated with the respective PRN code can be detected from the power density spectrum at the output of block 808, having a peak at the respective frequency shift.
Another conventional concept for a parallel code phase search acquisition is depicted in FIG. 9. This method parallelizes the time search. As can be seen from FIG. 9, there are two multipliers 902 and 904 for multiplying a locally generated carrier signal with the incoming signal. The carrier signal is generated by the local oscillator 906, where one copy of the locally generated carrier signal is phase-shifted by the phase shifter 908 in order to obtain the quadrature component. The resulting in-phase and quadrature components are then transformed to the frequency domain by the FFT depicted in block 910. It is to be noted that in this example the frequency Doppler bins, or frequency bins or frequency shifts, are searched in a serial manner, while, as will be explained in further detail in the following, the code bins are solved in parallel. In this example, a local PRN code generator 912 generates a local copy of the desired code. The desired code is then transformed to the frequency domain by the FFT 914, where additional processing evaluates the conjugate complex of the frequency transformed copy of the desired code in block 916. A multiplier 918 multiplies the output of the FFT 910 and the output of the conjugate complex block 916. The result will be a phase-shifted power density spectrum, where the phase-shift comes from the time shift of the incoming signal in the time domain. An inverse FFT block 920 will transform the results to the time domain. The phase shift in the frequency domain will result in a time shift in the time domain. By evaluating the power distribution of the time domain signal in block 922, a shifted peak can be determined, corresponding to the cross correlation function of the incoming signal and the respective locally generated desired code. From the shifted peak the time shift or code bin can be determined by threshold detection.
In other words, the FFT 914 allows for parallel search of the code bins. As the number of code bins may be much higher than the number of Doppler bins or frequency shift, the parallelization of the time search may be the fastest conventional method. Note, that this fact may not be true when long coherent integration times are performed, however, it may be fastest for proper SNR conditions. Low SNR conditions may need longer coherent integration times, for which the relations between a number of Doppler bins and the number of code bins may be different. However, two FFT operations, in FIG. 9 depicted as FFT 914 and IFFT (inverse FFT) 920 are utilized to reach the desired output. However, due to the number of code-phase bins, the length of these FFTs is larger than the parallel frequency space search acquisition. To some extent, there is a trade-off between complexity, i.e. the size of the FFTs, which are carried out and the number of iterations, which have to be carried out.